package bm8;

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * @date 2023/7/20 23:04
 * BM8.链表中倒数最后 k 个节点
 * https://www.nowcoder.com/practice/886370fe658f41b498d40fb34ae76ff9?tpId=295&tqId=1377477&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj
 */
public class Solution {

    // 快慢指针思想
    public ListNode FindKthToTail (ListNode pHead, int k) {
        // 定义快慢指针
        ListNode fast = pHead;
        ListNode slow = pHead;
        // 快指针先走 k 步
        while (k-- != 0) {
            if (fast != null) {
                fast = fast.next;
            } else {
                // 说明链表不足 k 个节点
                return null;
            }
        }
        // 快慢指针同时走
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }

    private static class ListNode {
        int val;
        ListNode next = null;
        public ListNode(int val) {
            this.val = val;
        }
    }
}
